package algebra.query.indexing;

import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import algebra.query.od.OrderDep;
import algebra.query.od.OrderDepFeature;
import algebra.visitors.cursors.CACursorDIOrderById;
import algebra.visitors.cursors.CACursorDIOrderByUn;

import kb.DescriptionLogicsKB;
import reasoner.KBReason;
import utils.Display;
import utils.exception.CoreReasoningException;
import utils.exception.OrderingDescriptionException;
import entities.assertion.ConceptAssertion;
import entities.concept.Concept;
import entities.concept.DomainConcept;
import entities.role.Role;

public class DescriptionIndex {
	private IndexTreeNode root;
	private final OrderDep od;
//	private List<ConceptAssertion> CAs;
	private int size = 0;
	public static boolean SAME_IND_RESTRICTION = true;
	//stat on selectivity and sufficient descriptiveness
	private int majorSortValues = 0;
	private int numOfTops = 0;
	private Set<String> values;
	private Role f;
	
	public int getSize(){
		return size;
	}
	
	public int getNumTops(){
		return this.numOfTops;
	}
	
	public int getNumOfFeatureValues(){
		return this.majorSortValues;
	}
	// ////// Constructors
	public DescriptionIndex(IndexTreeNode root, OrderDep od) {
		// WARNING: Shallow copy!
		this.root = root;
		this.od = od;
		initStat();
	}

	public DescriptionIndex(OrderDep od) {
		this.od = od;
		initStat();
	}
	
	public void initStat(){
		values = new HashSet<String>();
		//feature values only meaningful if the sort is on some feature (note: sort on id will be handled by cursor)
		if(this.od instanceof OrderDepFeature){
			f = this.od.asOdFeature().getOdFeature(); 
		}
	}

	
	public void incSize(){
		size ++;
	}
	
	private void getStat(Concept c){
		boolean once = false;
		for(Concept con : Concept.reduceToConjuncts(c)){
			if(!once && con.isTop()){
				this.numOfTops ++;
				once = true;
			}else if(f!=null && con instanceof DomainConcept){
				DomainConcept<?,?> dc = (DomainConcept<?, ?>) con;
				if(dc.getRealFeature().equals(f)){
					Object s = dc.getRealValue();
					if(s!=null){
						values.add((String) s);
					}
				}
			}
		}
		
	}


	public void insert(ConceptAssertion ac)
			throws OrderingDescriptionException, CoreReasoningException {
		this.incSize();
		this.getStat(ac.getConcept());
		if (root == null) {
			root = new IndexTreeNode(ac);
		} else {
			TreeUtils.insert(root, od, ac);
		}
//		TreeUtils.insert(root, od, ac);
	}

	public void remove(ConceptAssertion ac)
			throws OrderingDescriptionException, CoreReasoningException {
		TreeUtils.remove(root, od, ac);
	}
	
	public IndexTreeNode getNextNoSort(ConceptAssertion query,
			IndexTreeNode curNode, boolean star, DescriptionLogicsKB inputKB,
			CACursorDIOrderByUn cur) throws OrderingDescriptionException,
			CoreReasoningException {
		if (curNode == null) {
			return null;
		} else {
			return this.searchSinglePipelinedNoSort(query, curNode, star, inputKB,
					cur);
		}
	}
	
	//note: in general this input KB must be null
	private IndexTreeNode searchSinglePipelinedNoSort(ConceptAssertion query,
			IndexTreeNode node, boolean star, DescriptionLogicsKB inputKB,
			CACursorDIOrderByUn cur) throws OrderingDescriptionException,
			CoreReasoningException {
		if (node == null) {
			return null;
		}
		ConceptAssertion originalQuery = query;
		if (star) {
			Concept c = query.getConcept();
			query = new ConceptAssertion(node.getNodeAssertion()
					.getIndividual(), c);
		}
		IndexTreeNode ret = null;
		int compare = od.compare(query, node.getNodeAssertion());
		if (compare < 0) {
			return searchSinglePipelinedNoSort(originalQuery, node.getLeft(), star,
					inputKB, cur);
		} else if (compare > 0) {
			IndexTreeNode rightsub = null;
			if(!node.thread){
				rightsub = node.getRight();
			}
			return searchSinglePipelinedNoSort(originalQuery, rightsub, star,
					inputKB, cur);
		} else {
			// od 0 means query CA and node CA are equal/*incomparable*.
			if (!SAME_IND_RESTRICTION
					|| query.getIndividual().equals(
							node.getNodeAssertion().getIndividual())) {
				boolean ok = isQualifiedAnswerToQuery(query, node, inputKB);
				if(ok){
					ret = node;
				}
			}

			if (!cur.repetition()) {
				cur.initSubCursor(originalQuery, node.getLeft(), 0);
				cur.advanceSubCursor(0);
				cur.setMiddle(ret);
				IndexTreeNode rightsub = null;
				if(!node.thread){
					rightsub = node.getRight();
				}
				cur.initSubCursor(originalQuery, rightsub, 1);
				cur.advanceSubCursor(1);
			}
		}
		return cur.getNextFromThree();
	}



	public IndexTreeNode getNextSortId(ConceptAssertion query,
			IndexTreeNode curNode, boolean star, DescriptionLogicsKB inputKB,
			CACursorDIOrderById cur, boolean rod) throws OrderingDescriptionException,
			CoreReasoningException {
		if (curNode == null) {
			return null;
		} else {
			return this.searchSinglePipelined(query, curNode, star, inputKB,
					cur, rod);
		}
	}

	// private boolean repeat = false;
	public static int count = 0;

	//note: in general this input KB must be null
	private IndexTreeNode searchSinglePipelined(ConceptAssertion query,
			IndexTreeNode node, boolean star, DescriptionLogicsKB inputKB,
			CACursorDIOrderById cur, boolean resultOd) throws OrderingDescriptionException,
			CoreReasoningException {
		if (node == null) {
			return null;
		}
//		if(node.getID().toString().contains("Fujifilm_FinePix_J10_inst")){
//			System.out.println("here");
//		}
		ConceptAssertion originalQuery = query;
		if (star) {
			Concept c = query.getConcept();
			query = new ConceptAssertion(node.getNodeAssertion()
					.getIndividual(), c);
		}
		IndexTreeNode ret = null;
		int compare = od.compare(query, node.getNodeAssertion());
		if (compare < 0) {
			return searchSinglePipelined(originalQuery, node.getLeft(), star,
					inputKB, cur, resultOd);
		} else if (compare > 0) {
			IndexTreeNode rightsub = null;
			if(!node.thread){
				rightsub = node.getRight();
			}
			return searchSinglePipelined(originalQuery, rightsub, star,
					inputKB, cur, resultOd);
		} else {
			// od 0 means query CA and node CA are equal/*incomparable*.
			if (!SAME_IND_RESTRICTION || query.getIndividual().equals(
							node.getNodeAssertion().getIndividual())) {
				boolean ok = isQualifiedAnswerToQuery(query, node, inputKB);
				if(ok){
					ret = node;
				}
			}
			// the query is not well ordered before or after root.
			// get next from left subtree, L; get one from right subtree, R; get
			// root C; Whichever ordered first among the three, return it.
			if (!cur.repetition()) {
				IndexTreeNode rightsub = null;
				if(!node.thread){
					rightsub = node.getRight();
				}
				cur.initSubCursor(originalQuery, node.getLeft(), rightsub);
				cur.populateSubCursor(0);
				cur.pushMiddleInThree(ret);
				cur.populateSubCursor(1);
			}
//			return cur.getNextFromThree();
		}
		return ret;
	}

	public static boolean isQualifiedAnswerToQuery(ConceptAssertion query, IndexTreeNode node, DescriptionLogicsKB kb) 
			throws CoreReasoningException{
		ConceptAssertion cand = node.getNodeAssertion();
		Concept qc = query.getConcept(), cc = cand.getConcept();
		if(qc.equals(cc)){
			return true;
		}
		if(qc.isTop()){
			//we never cache unsat concepts, so just return all concepts
			return true;
		}else if(cc.isTop()){
			//query is not top, this candidate is not an answer.
			return false;
		}
		KBReason res = new KBReason(false);
		count++;
		if (res.logicConsequence(cand, query, kb)) {
			return true;
		}
		return false;
	}
	



	// ///// Getters and Setters
	public IndexTreeNode getRoot() {
		return root;
	}


	public OrderDep getOd() {
		return od;
	}

	public String getVersion(String si) {
		// reasoner version, timestamp
		String ret = "";
		// ret += Display.COMMENTS+"\t" + KBReason.release_info +"\n";
		ret += Display.COMMENTS + "\t" + si + "\n";
		// ret += Display.COMMENTS+"\t" + new Date().toString()+"\n";
		return ret;
	}

	public void writeIndex(String src, OutputStream s, String encoding) {
		if (this.root == null) {
			return;
		}
		if (encoding == null || encoding.trim().equals("")) {
			encoding = "UTF8";
		}
		Writer out = null;
		try {
			out = new OutputStreamWriter(s, encoding);
			out.write(getVersion(src));
			String node = this.root.writeIndexNode("", "\n", "");
			out.write(node);
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

	public void print(OutputStream out) {
		if (this.root == null) {
			return;
		}
		this.root.print(out, "", "\n");
	}

	public void print(OutputStream out, String prefix, String newline) {
		if (this.root == null) {
			return;
		}
		this.root.print(out, prefix, newline);
	}

	public void load(List<ConceptAssertion> cas)
			throws OrderingDescriptionException, CoreReasoningException {
		for (ConceptAssertion ca : cas) {
			this.insert(ca);
		}
		this.postProcessing();
	}
	
	public void postProcessing(){
		//finalize stat
		this.majorSortValues = this.values.size();
		this.values = null;
		//balance the tree
		this.root = TreeUtils.tree_to_vine(this.root);
		this.root = TreeUtils.vine_to_tree(this.root, size);
		return;
	}

	public List<ConceptAssertion> getAllConceptAssertions() {
		List<ConceptAssertion> res = new ArrayList<ConceptAssertion>();
		IndexTreeNode node = this.getThreadedFirst();
		while(node != null){
			res.add(node.getNodeAssertion());
			node = this.getThreadedNext(node);
		}
		return res;
	}
	
	//pipelined in-order traversal
	public IndexTreeNode getThreadedFirst(){
		IndexTreeNode cur = root;
		if(cur != null){
			while(cur.getLeft()!=null){
				cur = cur.getLeft();
			}
		}
		return cur;
	} 
	
	//note: the rightmost node still has thread true, but points to a leaf node (not a thread like others).
	public IndexTreeNode getThreadedNext(IndexTreeNode cur){
		if(!cur.thread){
			cur = cur.getRight();
			if(cur!=null){
				while(cur.getLeft() != null){
					cur = cur.getLeft();
				}
			}
		}else{
			cur = cur.getRight();
		}
		return cur;
	}

}
